package other;

import java.util.ArrayList;
import java.util.Arrays;

public class BackpackProblem {
    public static void main(String[] args) {
        ArrayList<ThingInBackpack> list = new ArrayList<>();
        ThingInBackpack thing = new ThingInBackpack(1,1500,"吉他");
        list.add(thing);
        thing = new ThingInBackpack(4,3000,"音响");
        list.add(thing);
        thing = new ThingInBackpack(3,2000,"电脑");
        list.add(thing);
        int result = getBest(list,4);
        System.out.println("最佳方案:"+result);
    }

    public static int getBest(ArrayList<ThingInBackpack> things,int totalWeight){
        int[][] bv = new int[things.size()+1][totalWeight+1];
        int[] v = new int[things.size()+1];
        int[] w = new int[things.size()+1];
        for(int i=1;i<things.size()+1;i++){
            v[i] = things.get(i-1).getValue();
            w[i] = things.get(i-1).getWeight();
        }
        for(int i=1;i<things.size()+1;i++){
            for(int j=1;j<totalWeight+1;j++){
                if(w[i]>j){
                    bv[i][j]=bv[i-1][j];
                }else {
                    bv[i][j]=Math.max(bv[i-1][j],v[i]+bv[i-1][j-w[i]]);
                }
            }
        }
        for(int[]a:bv){
            System.out.println(Arrays.toString(a));
        }

        return bv[things.size()][totalWeight];
    }
}
class ThingInBackpack{
    private int weight;
    private int value;
    private String name;

    public ThingInBackpack() {
    }

    public ThingInBackpack(int weight, int value, String name) {
        this.weight = weight;
        this.value = value;
        this.name = name;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}
